Discrete Logarithm Problem

释义 Definition

离散对数问题：在有限群（常见为模素数乘法群或椭圆曲线群）中，已知生成元 (g) 和元素 (h)，要求找到整数 (x) 使得 (g^x = h)（或 (g^x \equiv h \pmod p)）。它被认为在合适参数下计算困难，是多种公钥密码体制安全性的基础之一。（在不同群上难度与算法会有所差异。）

发音 Pronunciation (IPA)

/dɪˈskriːt ˈlɔːɡərɪðəm ˈprɑːbləm/

例句 Examples

The security of Diffie–Hellman depends on the discrete logarithm problem.
迪菲–赫尔曼密钥交换的安全性依赖于离散对数问题。

In a cyclic group of large prime order, solving the discrete logarithm problem efficiently would undermine many public-key systems.
在大素数阶的循环群中，如果能高效求解离散对数问题，将会削弱许多公钥系统的安全性。

词源 Etymology

该术语由三部分构成：discrete（“离散的”，指对象在有限/可数集合中）、logarithm（“对数”，源自希腊语词根，意为“比例的推理/计算”）、problem（“问题”）。合在一起表示“在离散结构（如有限群）里求对数”的计算难题；这里的“对数”是“指数的逆运算”的类比，但发生在模运算或群运算的语境中。

相关词 Related Words

• Cyclic Group
• Diffie–Hellman
• Discrete Logarithm
• Elliptic Curve Cryptography
• Generator
• Modular Arithmetic
• Public-Key Cryptography
• Computational Hardness

文献与作品 Literary / Notable Works

• Handbook of Applied Cryptography（Menezes, van Oorschot, Vanstone）：系统讨论离散对数问题及其在密码中的应用与算法。
• Introduction to Modern Cryptography（Katz & Lindell）：以现代安全定义框架讲述基于离散对数相关假设的协议。
• Cryptography: Theory and Practice（Douglas R. Stinson）：教材中常以离散对数问题为核心计算难题之一进行介绍。
• Applied Cryptography（Bruce Schneier）：在公钥算法与密钥交换章节中多次提及离散对数相关问题。